package org.skywork.top.core.algorithm.str;

/**
 * 二进制求和
 */
public class no_67 {

    /**
     * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     */
    public static String addBinary(String a, String b) {

        /**
         * 示例 1：
         * 输入:a = "11", b = "1"
         * 输出："100"
         *
         * 示例 2：
         * 输入：a = "1010", b = "1011"
         * 输出："10101"
         */
        if(a.length() == 0){
            return b;
        }

        if(b.length() == 0){
            return a;
        }

        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        char[] temp = aChars;
        if(bChars.length > aChars.length){
            temp = bChars;
            bChars = aChars;
        }
        int num = bChars.length - 1;
        String c = "";
        boolean add = false;
        for(int i = temp.length - 1; i >= 0; i--){
            if(num >= 0){
                if((temp[i] == '1' && bChars[num] == '1')){
                    if(add){
                        c = "1" + c;
                    }else{
                        c = "0" + c;
                    }
                    add = true;
                }else if(temp[i] == '0' && bChars[num] == '0'){
                    if(add){
                        c = "1" + c;
                        add = false;
                    }else{
                        c = "0" + c;
                    }
                }else{
                    if(add){
                        c = "0" + c;
                    }else{
                        c = "1" + c;
                    }
                }
            }else{
                if(add){
                    if(temp[i] == '1'){
                        c = "0" + c;
                    }else{
                        c = "1" + c;
                        add = false;
                    }

                }else{
                    c = temp[i] + c;
                }
            }
            num--;
        }
        if(num < 0 && add){
            c = "1" + c;
        }
        return c;
    }

    public static String addBinary2(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");
        return ans.reverse().toString();
    }

    public static void main(String[] args) {
        String a = "110010";
        String b = "10111";
        System.out.println(addBinary(a, b));
    }
}
